package main.leetcode.offer.secondround.from51to68;

/** 51.数组中的逆序对 */
public class ex51 {
    private int[] aux;
    private int res;

    public int reversePairs(int[] nums) {
        if (nums == null || nums.length == 0) {
            return res;
        }
        int n = nums.length;
        aux = new int[n];
        int[] tmp = nums.clone();
        mergeSort(tmp, 0, n - 1);
        return res;
    }

    private void mergeSort(int[] num, int l, int r) {
        if (l >= r) {
            return;
        }
        int mid = l + (r - l >>> 1);
        mergeSort(num, l, mid);
        mergeSort(num, mid + 1, r);
        if (num[mid] <= num[mid + 1]) {
            return;
        }
        merge(num, l, mid, r);
    }

    private void merge(int[] num, int l, int mid, int r) {
        System.arraycopy(num, l, aux, l, r - l + 1);
        int i = l, j = mid + 1;
        for (int k = l; k <= r; ++k) {
            if (i > mid) {
                num[k] = aux[j++];
            } else if (j > r) {
                num[k] = aux[i++];
            } else if (aux[i] > aux[j]) {
                num[k] = aux[j++];
                //     ⬇     ⬇
                // 1 2 7 8 | 3 4 5 6
                res += mid - i + 1;
            } else {
                num[k] = aux[i++];
            }
        }
    }
}
